package com.wtgroup.demo.mianshi.算法.排序2305;

import java.util.Arrays;
import java.util.Random;
import java.util.function.Supplier;

import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Tools;

/*
 * # 插入排序 & 希尔排序
 *
 * ## 基本思想
 *
 * ## 和冒泡， 选择比较
 *   - 10万的数组: 插入2487ms，
 *
 * ## 和堆排序比较
 *   - 1亿，堆排序： 35693ms，
 *
 * 总结: 推荐堆排序, 几乎是选择, 冒泡, 插入的100倍
 *
 * ## 插入排序和希尔排序比较
 * 数组: MyUtils.randomArr(100000, 10000,-123)
 * - 插入排序: 2598ms
 * - 希尔排序: 37ms
 * 希尔排序是插入排序的70倍!
 *
 * - 直接插入排序是*稳定*的
 * - 希尔排序是*不稳定*的, 因为是间隔h的插入, 例如.. 8,8,... 当指向第一个8的时候, 刚好和后面的较小的数对换了,
 *   而后续后一个8又一直较小, 最后后移移到第一个8的前面去了. 这样就出现了不稳定性.
 *
 *
 * 结论:
 * 	- 希尔排序接近堆排序
 *
 *
 * 希尔排序不同的 gap 选取策略, shellSort2 是普通 100 倍, shellSort 仅个数倍
 *
 */

/**
 * 插入排序
 *
 * Tip: 想象打扑克抓牌整理牌顺序.
 * 抓到一张牌, 从后往前比对, 比当前大的后移1位.
 * 直到遇到小或等的, 放到它后面.
 *
 * 稳定
 *
 * @author Nisus
 *
 */
public class InsertSort {
	public static void main(String[] args) {
		// int[] arr = MyUtils.randomArr(100000, 10000, 123);
		// int[] arr = MyUtils.randomArr(30,100,-123);
		// int[] arr = {3,4,1,5,8};
		// System.out.println(Arrays.toString(arr));
		/** 耗时测算 **/
		// int[] arr = RandomUtil.randomArray(100000, 0, 10000, -123);
		// long t0 = System.currentTimeMillis();
		// // insertSort(arr);
		// shellSort(arr);
		//
		// long t1 = System.currentTimeMillis();
		// System.out.println((t1 - t0) + "ms");

		Judger.of(() -> {
			int[] arr1 = RandomUtil.randomArray(10000, 0, 10000, -123);
			shellSort(arr1);
			int[]  arr2 = Arrays.copyOf(arr1, arr1.length);
			insertSort(arr2);

			return Tools.equals(arr1, arr2);
		}).setIterCount(100).start().print();
	}

	private static void testTime() {
		////////////////////////////////////////////////////////////////////
		/* 算法测试代码块 */
		long alg1_usedtime = 0;
		long alg2_usedtime = 0;
		int i = 0;

		while (i < 1) {
			int seed = new Random().nextInt(1000000);
			int[] arr1 = RandomUtil.randomArray(100000, 0, 10000, seed);
			int[] arr2 = RandomUtil.randomArray(100000, 0, 10000, seed);

			long cost1 = Tools.time("插入排序", () -> {
				insertSort(arr1);
			});

			long cost2 = Tools.time("希尔排序", () -> {
				shellSort2(arr2);
			});

			alg1_usedtime += cost1;
			alg2_usedtime += cost2;
			i++;
		}

		System.out.println("算法1:" + alg1_usedtime + "ms");
		System.out.println("算法2:" + alg2_usedtime + "ms");
		double alg1_usedtime_d = (double) alg1_usedtime;
		double mul = alg1_usedtime_d / alg2_usedtime;
		System.out.println(mul + "倍");
		//////////////////////////////////////////////////////////////////////////////
	}

	/*
	 * ## 插入排序
	 */
	public static void insertSort(int[] arr) {
		// int count=0;
		int N = arr.length;
		for (int i = 1; i < N; i++) {
			// 当前抓到的牌
			int curr = arr[i];
			// 前面的都是已经排好序的
			int j = i - 1;
			while (j >= 0 && curr < arr[j]) { // 注意和有序区对比时, 从后往前比, 这样大概率会减少比较次数
				arr[j+1] = arr[j];
				j--;
			}
			arr[j+1] = curr; // 交换步骤分开放, 避免多余的无意义的访问数组
		}
		// System.out.println(count);
	}

	/**
	 * 更贴近直觉
	 *
	 * 普通插入排序, 交换太慢了, 相邻交换.
	 * 增大交换距离.
	 * 长距离->短距离, 最中gap=1, 就是普通的插入排序, 最终一定能有序.
	 * 但由于前面的长距离交换, 整个数组相对有序, gap小时, 插入会更快.
	 */
	public static void shellSort(int[] arr) {
		int N = arr.length;
		for (int gap = N / 2; gap > 0; gap /= 2) {
			for (int i = 1; i < N; i += gap) {
				int curr = arr[i];
				int j = i - gap;
				while (j >= 0 && arr[j] > curr) {
					arr[j + gap] = arr[j];
					j -= gap;
				}
				arr[j + gap] = curr;
			}
		}
	}

	/*
	 * ## 希尔排序
	 * 对于大规模乱序数组插入排序很慢， 因为它只会交换相邻的元素， 因此元素只能一点一点地从数组
	 * 的一端移动到另一端。 例如， 如果主键最小的元素正好在数组的尽头， 要将它挪到正确的位置就需
	 * 要 N-1 次移动。 希尔排序为了加快速度简单地改进了插入排序， 交换不相邻的元素以对数组的局部
	 * 进行排序， 并最终用插入排序将局部有序的数组排序。
	 *
	 * - 《算法》书中i位移1，j位移h，但同时实现了比较和交换（如果满足条件），接下来可以继续进行一下个i。
	 * 但我这里比较和交换拆开的机制，所以不能照搬这个思路。而只能等到本次的间隔为h的子数组排完之后，才能进入下一次的i。
	 */
	public static void shellSort2(int[] arr) { // 复杂了
		int N = arr.length;
		int h = 1;
		int temp = 0;
		// 获得初始间隔大小
		while (h < N / 3) {
			h = 3 * h; // 保证h是3的倍数, 后面按3倍逐步缩小 1 3 9 27 81 ...
		}
		int h_i = 0; // (k-1)*h~k*h间自增1
		while (h >= 1) {
			h_i = h;
			while (h_i < 2 * h) {
				for (int i = h_i; i < N; i += h) {
					temp = arr[i];
					int j = i;
					while (j >= h && temp < arr[j - h]) {
						arr[j] = arr[j - h];
						j -= h;
					}
					arr[j] = temp;
				}

				h_i++; // 更新i的初始值
			}
			h = h / 3;
		}
	}

}
